#include "dunGraphs.h"

t_graph graphCreate(int order)
{
	t_graph	g;
	int		i;
	g = malloc(GSIZE(order));
	g->order = order;
	for (i=0; i<order; i++)
	{
		room(g,i) = malloc(sizeof(struct s_som));
		room(g,i)->som = i;
		room(g,i)->room = Normal;
		room(g,i)->value = 0;
		succ(g,i) = pred(g,i) = NULL;
	}
	return g;
}

void graphAddArc(t_graph g, int s, int d, float c)
{
	t_adj		pa;
	pa = malloc(sizeof(struct s_adj));
	pa->cost = c;
	pa->vsom = d;
	pa->next = succ(g,s);
	succ(g,s) = pa;
	pa = malloc(sizeof(struct s_adj));
	pa->cost = c;
	pa->vsom = s;
	pa->next = pred(g,d);
	pred(g,d) = pa;
}

void graphPrint(t_graph g)
{
	t_som ps;
	t_adj pa;
	dunQueue f = queueNew();
	int *M = malloc(g->order * sizeof (int));
	int x = 0;
	f = queuePush(1, f);
	
	for (x = 0; x < g->order; x++)
	{
		M[x] = 0;
	}
	
	do
	{
		x = queuePop(&f);
		ps = g->lsom[x];
		printf("ROOM %d is a", x);
		if (ps->room == Normal)
			printf(" NORMAL Room\n");
		
		if (ps->room == Monster)
			printf(" MONSTER Room of level %d\n", ps->value);
		
		if (ps->room == Brewery)
			printf(" BREWERY Room which gives %d life\n", ps->value);
		
		if (ps->room == Dead)
			printf(" DEAD Room\n");
		
		for (pa = ps->succ; pa; pa = pa->next)
		{
			if (!M[pa->vsom])
			{
				M[pa->vsom] = x;
				f = queuePush(pa->vsom, f);
				printf("ARC: %d -> %d\n", x, pa->vsom);
			}
		}
	} while (!queueIsEmpty(f));
}

int graphComputeCost(t_graph g, int life, dunQueue verts)
{
	t_som ps;
	t_adj pa;
	int x = queuePop(&verts);
	int y;
	while ((!queueIsEmpty(verts)) && (life > 0))
	{
		ps = g->lsom[x];
		y = queuePop(&verts);
		pa = ps->succ;
		while ((pa) && (pa->vsom != y))
		{
			pa = pa->next;
		}
		if (!pa)
			return (_NP_);
		else
			if (g->lsom[y]->room == Dead)
			return (_DEAD_);
		else
		{
			life -= g->lsom[y]->value + pa->cost;
			x = y;
		}
	}
	if (life <= 0)
		return (_DEAD_);
	else
		return (life);
}

dunQueue graphSeekPath(t_graph g, int life, int s, int d)
{
	dunQueue f = queueNew();
	dunQueue* pere = calloc(g->order, sizeof (dunQueue));
	int i;

	life = graphDijkstra(g, s, d, life, pere);
	if (life)
	{
		f = stackPush(d, f);
		while (d != s)
		{
			if (pere[d] == NULL)
			{
				d = i;
				stackPop(&f);
			}
			else
			{
				i = d;
				d = stackPop(&pere[d]);
				f = stackPush(d, f);
			}
		}
	}
	free(pere);
	return (f);
}

int graphDijkstra(t_graph g, int src, int dst, int life, dunQueue* pere)
{
	t_som ps, ps2;
	t_adj pa;
	float* ppd = malloc(g->order * sizeof (float));
	float* hd = malloc(g->order * sizeof (float));
	t_heap h = heapCreate(1024);
	int i, l, r;
	
	for (i = 0; i < g->order; i++)
	{
		ppd[i] = 0;
		hd[i] = FLT_MAX;
	}
	EMPILER(pere, src, src);
	ppd[src] = 0;
	hd[src] = heur(g, src, life, dst, ppd);
	heapAdd(&h, src, life, life);
	do
	{
		heapExtractMin(&h, &src, &life);
		ps = g->lsom[src];
		for (pa = ps->succ; pa; pa = pa->next)
		{
			r = pa->vsom;
			ps2 = g->lsom[r];
			if (ps2->room != Dead)
			{
				l = life - pa->cost - g->lsom[r]->value;
				if ((l > 0))
				{
					if (ppd[r] < l)
					{
						ppd[r] = l;
						EMPILER(pere, r, src);
						hd[r] = ppd[r] + heur(g, r, l, dst, ppd);
						heapUpdate(&h, r, l, hd[r]);
					}
				}
			}
		}
	} while ((src != dst) && (!heapIsEmpty(h)));
	heapFree(h);
	heur(g, -1, 0, 0, ppd);
	free(ppd);
	free(hd);
	if (src == dst)
		return (dst);
	else
		return (0);
}

void	graphRelaxArc(t_heap *h, int ps, t_adj pa, int* pere, int *dist)
{
	int i = pa->vsom;
	if ((pere[i] >= 0) && (dist[i] > (dist[ps] + pa->cost)))
	{
		dist[i] = dist[ps] + pa->cost;
		pere[i] = ps;
		heapUpdate(h, i, i, dist[i]);
	}
}

void graphGetStates(t_graph g, int s, int life, dunQueue* outLife, dunQueue* outRoom)
{
	t_som ps = g->lsom[s], ps2;
	t_adj pa;
	int tmp_life, tmp_room;
	for (pa = ps->succ; pa; pa = pa->next)
	{
		tmp_life = life;
		tmp_room = pa->vsom;
		ps2 = g->lsom[tmp_room];
		if (ps2->room != Dead)
		{
			tmp_life -= pa->cost + ps2->value;
			if (tmp_life > 0)
			{
				*outLife = queuePush(tmp_life, *outLife);
				*outRoom = queuePush(tmp_room, *outRoom);
			}
		}
	}
}

float heur(t_graph g, int som, int life, int dst, float* dist)
{
	static int* man = NULL;
	static int dest = 0;
	float f;
	life = life;
	dist = dist;
	
	if (!man)
	{
		man = computeManhattan(g, dst);
		dest = dst;
	}
	
	if (som < 0)
	{
		free(man);
		man = NULL;
		return (0);
	}
	
	f = (float)man[som];
	f /= (float)dist[som];
	return (f);
}

int* computeManhattan(t_graph g, int dst)
{
	int* man = calloc(g->order, sizeof (int)), y, dist = 0;
	dunQueue f = queueNew();
	t_adj pa;
	
	f = queuePush(dst, f);
	f = queuePush(0, f);
	do
	{
		dst = queuePop(&f);
		if (!dst)
		{
			if (queueIsEmpty(f))
				return (man);
			f = queuePush(0,f);
			dst = queuePop(&f);
			dist++;
		}
		for (pa = g->lsom[dst]->pred; pa; pa = pa->next)
		{
			y = pa->vsom;
			if (!man[y])
			{
				man[y] = dist;
				f = queuePush(y, f);
			}
		}
	} while (!queueIsEmpty(f));	
	return (man);
}